lib/Mi manual de algoritmos/version_maraton_nacional_2008/src/geometria/grahamscan.cpp

   1 /*
   2   Graham Scan.
   3  */
   4 #include <iostream>
   5 #include <vector>
   6 #include <algorithm>
   7 #include <iterator>
   8 #include <math.h>
   9 #include <stdio.h>
  10
  11 using namespace std;
  12
  13 const double pi = 2*acos(0);
  14
  15 struct point{
  16   int x,y;
  17   point() {}
  18   point(int X, int Y) : x(X), y(Y) {}
  19 };
  20
  21 point pivot;
  22
  23 ostream& operator<< (ostream& out, const point& c)
  24 {
  25   out << "(" << c.x << "," << c.y << ")";
  26   return out;
  27 }
  28
  29 inline int distsqr(const point &a, const point &b){
  30   return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
  31 }
  32
  33 inline double dist(const point &a, const point &b){
  34   return sqrt(distsqr(a, b));
  35 }
  36
  37 //retorna > 0 si c esta a la izquierda del segmento AB
  38 //retorna < 0 si c esta a la derecha del segmento AB
  39 //retorna == 0 si c es colineal con el segmento AB
  40 inline int cross(const point &a, const point &b, const point &c){
  41   return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
  42 }
  43
  44 //Self < that si esta a la derecha del segmento Pivot-That
  45 bool angleCmp(const point &self, const point &that){
  46   int t = cross(pivot, that, self);
  47   if (t < 0) return true;
  48   if (t == 0){
  49     //Self < that si está más cerquita
  50     return (distsqr(pivot, self) < distsqr(pivot, that));
  51   }
  52   return false;
  53 }
  54
  55 vector<point> graham(vector<point> p){
  56   //Metemos el más abajo más a la izquierda en la posición 0
  57   for (int i=1; i<p.size(); ++i){
  58     if (p[i].y < p[0].y || (p[i].y == p[0].y && p[i].x < p[0].x ))
  59       swap(p[0], p[i]);
  60   }
  61
  62   pivot = p[0];
  63   sort(p.begin(), p.end(), angleCmp);
  64
  65   //Ordenar por ángulo y eliminar repetidos.
  66   //Si varios puntos tienen el mismo angulo el más lejano queda después en la lista
  67   vector<point> chull(p.begin(), p.begin()+3);
  68
  69   //Ahora sí!!!
  70   for (int i=3; i<p.size(); ++i){
  71     while ( chull.size() >= 2 && cross(chull[chull.size()-2], chull[chull.size()-1], p[i]) <= 0){
  72       chull.erase(chull.end() - 1);
  73     }
  74     chull.push_back(p[i]);
  75   }
  76   //chull contiene los puntos del convex hull ordenados anti-clockwise.
  77   //No contiene ningún punto repetido.
  78   //El primer punto no es el mismo que el último, i.e, la última arista
  79   //va de chull[chull.size()-1] a chull[0]
  80   return chull;
  81 }